import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;

public class Solution647 {
    /**
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     * <p>
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "abc"
     * 输出: 3
     * 解释: 三个回文子串: "a", "b", "c".
     */

    public int countSubstrings(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int sum = 0;
        for (int center = 0; center <= 2 * n - 1; center++) {
            int l = center >> 1;
            int r = l + (center & 1);
            while (l >= 0 && r < n && chars[l] == chars[r]) {
                sum++;
                l--;
                r++;
            }
        }
        return sum;
    }

    // 马拉车算法
    public int countSubstrings2(String s) {
        int n = s.length();
        char[] arr = new char[2 * n + 3];
        arr[0] = '@';
        arr[1] = '#';
        arr[arr.length - 1] = '$';
        int t = 2;
        for (char c : s.toCharArray()) {
            arr[t++] = c;
            arr[t++] = '#';
        }
        int[] res = new int[arr.length];
        int center = 0, right = 0;
        for (int i = 1; i < res.length - 1; i++) {
            if (i < right) {
                res[i] = Math.min(right - i, res[2 * center - i]);
            }
            while (arr[i + res[i] + 1] == arr[i - res[i] - 1]) {
                res[i]++;
            }
            if (i + res[i] > right) {
                center = i;
                right = i + res[i];
            }
        }
        int ans = 0;
        for (int i : res) {
            ans += (i + 1) >> 1;
        }
        return ans;
    }

}
